Decision Trees

Tags: #◇Computer Science #◇CSINTSY #◇Decision Trees #◇Code Snippets #◇M4

◇Overview

A Decision Tree is a supervised machine learning model that predicts an outcome by learning a sequence of simple yes/no questions based on the dataset's features. The model builds a tree recursively from the root node to leaf nodes.

Building the Tree:
At each internal node, the algorithm must pick the "best" question to split the data. The best split is the one that most successfully separates the target classes, minimizing "impurity."

Handling Numerical Features:
For continuous/numerical features, the tree considers all unique values as potential threshold questions (e.g., Is weight >= 40?).

Stopping Criteria (Preventing Overfitting):
To avoid overfitting, trees use stopping criteria such as:

Minimum batch size to split a node (min_samples_split).
Maximum tree depth (max_depth).
Maximum number of terminal leaf nodes (max_leaf_nodes).
Minimum impurity reduction threshold ( $\Delta L$ ).

◇Theoretical Framework: Decision Tree Architecture & CART Induction

CART Recursive Splitting Pipeline

◇Code Implementation

(Algorithm relies on recursively calculating split impurity.)

◇Syntax Breakdown

(Not applicable)

◇Complexity Analysis

Gini Index (Impurity Measure for Classification):
$L(S) = 1 - \sum_{i} \left( \frac{p_i}{|S|} \right)^2$
Where $p_i$ is the number of instances of class $i$ in set $S$ . A Gini index of $0$ means the set is perfectly pure.

Split Gini Calculation:
The Gini index of a split is the weighted average of the Gini indices of the resulting subsets. The feature providing the lowest split Gini is chosen.

Variance (Impurity Measure for Regression):
For regression trees, variance is used instead of Gini to measure node purity:
$L(S) = \frac{1}{n-1} \sum (x - \mu)^2$
Leaf nodes then output the average value of the samples within that node.

Previous Topic: ◇Machine Learning Models
Next Topic: ◇Naive Bayes
Related Notes: ◇Decision Tree, ◇Inference for Categorical Data

DECISION TREES